package 剑指offer;

import 抽象数据类型.TreeNode;

import java.util.ArrayList;
import java.util.Arrays;

import static 抽象数据类型.TreeNode.buildTree;


/**
 * @description:
 * @author: ywk
 * @date: 2020-11-06
 */
public class 二叉树根节点到叶子节点和为指定值的路径 {
    public static void main(String[] args) {
        Integer[] str = new Integer[]{3, -1, 3, null, null, 1, 1};
        TreeNode treeNode = buildTree(new ArrayList<>(Arrays.asList(str)));
        System.out.println(pathSum(treeNode, 7));
    }

    /**
     * @param root TreeNode类
     * @param sum  int整型
     * @return int整型ArrayList<ArrayList       <>>
     */
    public static ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
        // write code here
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        pathSum(root, sum, 0, result, new ArrayList<>());
        return result;

    }

    private static void pathSum(TreeNode root, int sum, int curSum,
                                ArrayList<ArrayList<Integer>> result, ArrayList<Integer> list) {
        if (root == null) {
            return;
        }
        list.add((Integer) root.val);
        if (root.left == null && root.right == null) {
            if ((Integer) root.val + curSum == sum) {
                result.add(new ArrayList<>(list));
            }
        }
        pathSum(root.left, sum, curSum + (Integer) root.val, result, list);
        pathSum(root.right, sum, curSum + (Integer) root.val, result, list);
        list.remove(list.size() - 1);
    }

}
